// ******************************************************
// >> File Name: /home/diabio/project/al_cache/al_cache/lfu_cache.h
// >> Author: diabiolin
// >> Created Time: Thu 17 Apr 2025 01:44:54 PM CST
// >> Description:LFU algorithm
// ******************************************************
#pragma once 
#include "cache_policy.h"
#include <unordered_map>
#include <memory>
#include <mutex>
#include <cmath>
#include <vector>
#include <thread>

namespace al_cache{

template <typename Key, typename Value> class LfuCache;

template <typename Key, typename Value>
class FreqList{
private:
	struct Node {
		int key, value, freq;
		std::weak_ptr<Node> prev;
		std::shared_ptr<Node> next;
		Node() : key(0), value(0), freq(1), prev(), next() {} // 默认构造
		Node(int key, int value)
			: key(key), value(value), freq(1), prev(), next() {}
	};

	using NodePtr = std::shared_ptr<Node>;
	int freq_;
	NodePtr dummyHead_; // 虚拟头节点 
	NodePtr dummyTail_; // 虚拟尾结点

public:
	explicit FreqList(int n)
	: freq_(n)
	{
		dummyHead_ = std::make_shared<Node>();
		dummyTail_ = std::make_shared<Node>();
		dummyHead_->next = dummyTail_;
		dummyTail_->prev = dummyHead_;
	}
	~FreqList(){
		if (dummyHead_->next) {
			dummyHead_->next->prev.reset();
			dummyHead_->next = nullptr;
		}
		dummyTail_->prev.reset();
		dummyHead_ = nullptr;
		dummyTail_ = nullptr;
	}
	bool isEmpty() const {
		return dummyHead_->next == dummyTail_;
	}

	// 添加节点
	void addNode(NodePtr node){
		if(!node || !dummyHead_ || !dummyTail_){
			return;
		}
		node->prev = dummyTail_->prev;
		node->next = dummyTail_;
		if(auto prev = dummyTail_->prev.lock()){
			prev->next = node;
		}
		dummyTail_->prev = node;
		// node->prev = dummyTail_->prev;
		// node->next = dummyTail_;
		// dummyTail_->prev->next = node;
		// dummyTail_->prev = node;
	}

	void removeNode(NodePtr node){
		if(!node || !dummyHead_ || !dummyTail_){
			return;
		}

		if(auto prev = node->prev.lock()){
			prev->next = node->next;
		}

		if(node->next){
			node->next->prev = node->prev;
		}
		node->prev.reset(); // weak_ptr 需要reset
		node->next = nullptr;
		// if(!node->prev || !node->next){
		// 	return;
		// }
		// node->prev->next = node->next;
		// node->next->prev = node->prev;
		// node->prev = nullptr;
		// node->next = nullptr; 
	}

	NodePtr getFirstNode() const { return dummyHead_->next; }
	
	friend class LfuCache<Key, Value>;

};

template <typename Key, typename Value>
class LfuCache : public CachePolicy<Key, Value>{
public:
	using Node = typename FreqList<Key, Value>::Node;
	using NodePtr = std::shared_ptr<Node>;
	using NodeMap = std::unordered_map<Key, NodePtr>;

	LfuCache(int capacity, int maxAverageNum)
		: capacity_(capacity)
		, minFreq_(INT8_MAX)
		, maxAverageNum_(maxAverageNum)
		{}
	

	void put(Key key, Value value) override {
		if(capacity_ == 0){
			return;
		}
		std::lock_guard<std::mutex> lock(mutex_);
		auto it = nodeMap_.find(key);
		if(it != nodeMap_.end()){
			it->second->value = value;
			getCache(it->second, value);
			return;
		}
		putCache(key, value);
	} 

	bool get(Key key, Value &value) override {
		std::lock_guard<std::mutex> lock(mutex_);
		auto it = nodeMap_.find(key);
		if(it != nodeMap_.end()){
			getCache(it->second, value);
			return true;
		}
		return false;
	}

	Value get(Key key) override {
		Value value{};
		get(key, value);
		return value;
	}

private:
	int capacity_;  // 缓存容量
	int minFreq_;  // 最小访问频次
	int maxAverageNum_;  // 最大平均访问频次
	int curAverageNum_;  // 当前平均访问频次
	int curTotalNum_;  // 当前访问所有缓存次数总数 
	std::mutex mutex_;  // 互斥锁
	NodeMap nodeMap_;  // key -> node 
	std::unordered_map<int, std::unique_ptr<FreqList<Key, Value>>> freqToFreqList_;
	// std::unordered_map<int, FreqList<Key, Value>*> freqToFreqList_;  // freq -> freqList 

	// 添加缓存 
	void putCache(Key key, Value value);
	// 获取缓存 
	void getCache(NodePtr node, Value &value);
	// 移除过期资源
	void kickOut();
	// 从频率列表移除节点
	void removeFromFreqList(NodePtr node);
	// 添加到频率列表
	void addToFreqList(NodePtr node);
	// 增加平均访问等频率
	void addFreqNum();
	// 减少平均访问等频率
	void decreaseFreqNum(int num);
	// 处理当前平均访问频率超过上限的情况
	void handleOverMaxAverageNum();
	// 更新最小频率
	void updateMinFreq();
};

template <typename Key, typename Value>
void LfuCache<Key, Value>::putCache(Key key, Value value){
	if(nodeMap_.size() == capacity_){
		kickOut();
	}

	// 创建新节点
	NodePtr node = std::make_shared<Node>(key, value);
	nodeMap_[key] = node;
	addToFreqList(node);
	addFreqNum();
	minFreq_ = std::min(minFreq_, 1);
}

template <typename Key, typename Value>
void LfuCache<Key, Value>:: getCache(NodePtr node, Value &value){
	value = node->value;
	removeFromFreqList(node);
	node->freq++;
	addToFreqList(node);
	if(node->freq - 1 == minFreq_ && freqToFreqList_[node->freq - 1]->isEmpty()){
		minFreq_++;
	}
	addFreqNum();
}

template <typename Key, typename Value>
void LfuCache<Key, Value>::kickOut(){
	NodePtr node = freqToFreqList_[minFreq_]->getFirstNode();
	removeFromFreqList(node);
	nodeMap_.erase(node->key);
	decreaseFreqNum(node->freq);
}

template <typename Key, typename Value>
void LfuCache<Key, Value>::removeFromFreqList(NodePtr node){
	if(!node){
		return;
	}
	auto freq = node->freq;
	freqToFreqList_[freq]->removeNode(node);
}

template <typename Key, typename Value>
void LfuCache<Key, Value>::addToFreqList(NodePtr node){
	if(!node){
		return;
	}
	auto freq = node->freq;
	if(freqToFreqList_.find(node->freq) == freqToFreqList_.end()){
		// freqToFreqList_[node->freq] = new FreqList<Key, Value>(node->freq);
        freqToFreqList_[freq] = std::make_unique<FreqList<Key, Value>>(freq);
		
	}
	freqToFreqList_[freq]->addNode(node);
}

template <typename Key, typename Value>
void LfuCache<Key, Value>::addFreqNum(){
	curTotalNum_++;
	if(nodeMap_.empty()){
		curAverageNum_ = 0;
	}
	else{
		curAverageNum_ = curTotalNum_ / nodeMap_.size();
	}
	if(curAverageNum_ > maxAverageNum_){
		handleOverMaxAverageNum();
	}
}


template <typename Key, typename Value>
void LfuCache<Key, Value>::decreaseFreqNum(int num){
	// 减少平均访问频次和总访问频次
	curTotalNum_ -= num;
	if(nodeMap_.empty()){
		curTotalNum_ = 0;
	}
	else{
		curAverageNum_ = curTotalNum_ / nodeMap_.size();
	}
}

template <typename Key, typename Value>
void LfuCache<Key, Value>::handleOverMaxAverageNum(){
	if(nodeMap_.empty()){
		return;
	}

	// 当前平均访问频次超过最大平均访问频次，所有节点访问频次-（maxAverageNum_ / 2）
	for(auto it = nodeMap_.begin(); it != nodeMap_.end(); it++){
		if(!it->second){
			continue;
		}
		NodePtr node = it->second;

		removeFromFreqList(node);

		node->freq -= maxAverageNum_ / 2;
		if(node->freq < 1){
			node->freq = 1;
		}

		addToFreqList(node);
	}
	updateMinFreq();
}

template <typename Key, typename Value>
void LfuCache<Key, Value>::updateMinFreq(){
	minFreq_ = INT8_MAX;
	for(const auto &pair : freqToFreqList_){
		if(pair.second && !pair.second->isEmpty()){
			minFreq_ = std::min(minFreq_, pair.first);
		}
	}
	if(minFreq_ == INT8_MAX){
		minFreq_ = 1;
	}
}

// hash-lfu 
template<typename Key, typename Value>
class HashLfuCache : public CachePolicy<Key, Value>{
public:
	HashLfuCache(size_t capacity, int sliceNum, int maxAverageNum = 10)
		: sliceNum_(sliceNum > 0 ? sliceNum : std::thread::hardware_concurrency())
		, capacity_(capacity)
		{
			size_t sliceSize = std::ceil(capacity_ / static_cast<double>(sliceNum_));
			for(int i = 0; i < sliceNum_; i++){
				// lfuSliceCaches_.emplace_back(new LfuCache<Key, Value>(sliceSize, maxAverageNum));
                lfuSliceCaches_.emplace_back(std::make_unique<LfuCache<Key, Value>>(sliceSize, maxAverageNum));
			}
		}
	
	void put(Key key, Value value) override {
		size_t sliceIndex = Hash(key) % sliceNum_;
		lfuSliceCaches_[sliceIndex]->put(key, value);
	}

	bool get(Key key, Value &value) override {
		size_t sliceIndex = Hash(key) % sliceNum_;
		return lfuSliceCaches_[sliceIndex]->get(key, value);
	}

	Value get(Key key) override {
		Value value{};
		get(key, value);
		return value;
	}

private:
	size_t capacity_;  // 缓存容量 
	int sliceNum_;  // 切片数量 
	std::vector<std::unique_ptr<LfuCache<Key, Value>>> lfuSliceCaches_;

	// 私有方法 
	size_t Hash(Key key){
		std::hash<Key> hashFunc;
		return hashFunc(key);
	}
};

} // namespace al_cache 
